package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/reverse-linked-list/'>反转链表(Reverse Linked List)</a>
 * <p>给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5]
 *      输出：[5,4,3,2,1]
 *
 * 示例 2：
 *      输入：head = [1,2]
 *      输出：[2,1]
 *
 * 示例 3：
 *      输入：head = []
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>链表中节点的数目范围是 [0, 5000]</li>
 *         <li>-5000 <= Node.val <= 5000</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/10/31 15:22
 */
public class LC0206ReverseLinkedList_S {

    static class Solution {
        public ListNode reverseList(ListNode head) {
            // 如果没有节点或者只有一个节点，反转无意义
            if (head == null || head.next == null) {
                return head;
            }
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        Printer.printListNode(solution.reverseList(head1));
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        Printer.printListNode(solution.reverseList(head2));
        Printer.printListNode(solution.reverseList(null));

    }
}
